1. Field of the Invention
The present invention relates to a system and method for determining an optimal (or sufficiently near-optimal) solution to a shape-nesting problem (also commonly referred to as a “cutting-stock”, “trim-loss-minimization”, packing, or layout, problem, among other names), in one, two, or three dimensions, in which the pieces to be nested can be moved about in one, two, or three dimensions and possibly rotated so as to achieve a maximally dense nesting. The system and method of the invention include the data processing machine on which a program for determining the optimal solution runs, and the storage medium on which this program is stored.
2. Prior Art
Population-based, iterative improvement algorithms such as Genetic Algorithms (GAs) have been applied to a wide range of industrial problems. GAs are particularly effective at finding optimal, or near-optimal, solutions to problems with large numbers of decision variables and consequently large numbers of possible solutions (Genetic Algorithms in Search, Optimization, and Machine Learning, Goldberg, D. E., 1989).
One problem domain in which iterative, population-based approaches such as GAs have had some success is that of “shape nesting”. In many industries there is a need to cut many copies of a particular two dimensional shape from a two dimensional piece of material. For example, in the automobile industry, a particular shape of sheet steel needs to be cut from a large roll of sheet steel, to be later formed into a door panel for a new car. Often, the manufacturer wishes to cut as many of these “shaped pieces” as possible, from a single flat piece of raw material (herein known as the “substrate”). Maximizing the number of pieces cut from the substrate makes the most use of costly raw materials, minimizing “trim” or “waste”.
In another example of a shape-nesting domain, a user might wish to cut as many copies as possible of a particular dress pattern from a single bolt of cloth. Other real-world examples of shape nesting problems come from the paper industry and the wood products industry, all of which involve cutting small identical shapes from large “blanks” or “cutting stock” while minimizing unused substrate material (i.e., “trim”). “Resource-Based Fitness Sharing”, Horn, J., 2002, Parallel Problem Solving From Nature, PPSN VII, Lecture Notes in Computer Science 2439, provides more background on the problem domain, and more references to the literature and is incorporated herein by reference in its entirety.
Thus the challenge in many industries is to find an arrangement (sometimes called “nesting” or “layout”) of the shaped pieces on the substrate so that (1) there is no overlap between different pieces, (2) each shaped piece is entirely contained on the substrate (it is required to cut whole shapes out), and (3) the number of such non-overlapping, complete shaped pieces is maximized. This is, in general, a hard problem. In the general case, the pieces to be cut can have arbitrary shapes (e.g., the collar of a shirt, to be cut from a bolt of fabric), the substrate can have arbitrary shape (e.g., cutting identical flagstones from a rough slab of granite), and the placement of the pieces can include not only translational location (the x,y coordinate of the piece in the Cartesian plane) but also the orientation (angle), as the pieces can be rotated in order to make them “nest” more neatly and hence “pack” more closely.
Prior to this invention, genetic algorithms (GA) have been applied to shape-nesting problems in the literature. In most of these GA approaches, the shape-nesting problem was encoded in the “traditional way”, in that each individual chromosome in the population of chromosomes represented a complete solution to the nesting problem at hand. One limitation of this approach is that the chromosome becomes long and complex, due to the fact that it is encoding the entire solution, which means specifying the placement (that is, location and orientation) of each of the pieces on the substrate. Longer and more complex chromosomes make it more difficult and complex to design effective “discovery operators” (e.g., crossover, mutation), and require vastly more computation (i.e., larger population sizes and longer run times).
In his 1997 Ph.D. thesis, “The Nature of Niching: Genetic Algorithms and the Evolution of Optimal, Cooperative Populations” (1997), Jeffrey Horn introduced a “speciation approach”, in which the genetic algorithm is used to evolve a SET OF SPECIES, which together represent a solution to the shape-nesting problem at hand. Each chromosome in the population represents just one piece (by encoding the piece's location and orientation), with different subsets of the population representing different solutions to the problem at hand. This approach leads to simpler discovery operators, smaller population sizes, and shorter run times. Horn demonstrated the idea in a one dimensional nesting problem using “fitness sharing” (“Genetic algorithms with sharing for multimodal function optimization”, Goldberg, D. E., et al., 1987, Proceedings of the 2nd International Conference on Genetic Algorithms) to induce speciation. A fundamental limitation of fitness sharing is that it assumes each species occupies a fixed-radius “niche”. For shape nesting this means that the fitness sharing approach can only nest spherical shapes (e.g., circles in the two dimensional case). So Horn also suggested resource sharing as an alternative speciation method. (He did not implement resource sharing for shape nesting, nor did he discuss in any detail exactly how to do so.) Resource sharing would allow the nesting of pieces with arbitrary shapes.
Unfortunately, experiments and analysis since 1997 (Horn, 2002) indicate that resource sharing introduces instability to the GA, resulting usually in convergence to sub-optimal solutions.
So the current situation (which is the prior art with regard to iterative, population-based approaches to shape-nesting problems) can be summarized as follows:                1. GA approaches without speciation require large, complex chromosomes which in turn require complex GA operators, which together require massive computation,        2. “Speciation GA” approaches using fitness sharing greatly simplify the chromosome, operators, and computation required, but only work for nesting one shape: n-dimensional spheres (circles, in 2D), and        3. Speciation GA approaches using resource sharing work for arbitrary shapes, but perform very poorly.        
What is different about this invention is the use of a unique, new method of speciation in a GA (or similar, population-based, iterative improvement algorithm) applied to shape nesting: “resource-defined fitness sharing” (RFS). RFS is a synthesis of the fitness sharing and resource sharing processes for inducing species. RFS utilizes actual resource coverage, like resource sharing, so that pieces with arbitrary shape can be nested. But unlike resource sharing, and more like fitness sharing, RFS emphasizes pairwise interactions among species, and then sums the quantitative effects of the pairwise interactions to produce a single “niche count” for each individual in the population, similar to the niche count in fitness sharing, thereby avoiding the unstable and sub-optimal performance of resource sharing.